package 排序算法.插入排序;

import java.util.Comparator;

//直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)，平均时间复杂度为O(n2)。
//基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
public class Straight_Insertion_Sort {
    public static void main(String[] args) {
        int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
        //sortA(a);
        sortB(a);
    }

    //直接插入排序
    private static void sortA(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }


        //直接插入排序
        for (int i = 0; i < a.length; i++) {
            int temp = a[i]; //临时存放a[i]的值  进行后面的比较和插入操作
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (a[j] > temp) {
                    a[j + 1] = a[j];  //将大于temp的值一个个往后挪一位
                } else {
                    break;
                }
            }
            a[j + 1] = temp;
        }
        System.out.println("\n----------------------");
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    private static void sortB(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        //直接插入排序
        for (int i = 0; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            while (j > 0 && temp < a[j - 1]) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }

        System.out.println("\n----------------------");
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }

    }

}
